#include <bits/stdc++.h>

using namespace std;

// 字符串的全部子序列
// 子序列本身是可以有重复的，只是这个题目要求去重
// 测试链接 : https://www.nowcoder.com/practice/92e6247998294f2c933906fdedbc6e6a

class Solution 
{
private:
    void f1(string& s, string& path, int i, unordered_set<string>& set)
    {
        if(i == s.size())
        {
            set.emplace(path);
            return;
        }
        path.push_back(s[i]);
        f1(s, path, i + 1, set);
        path.pop_back();
        f1(s, path, i + 1, set);
    }

    void f2(string& s, string& path, int i, int size, unordered_set<string>& set)
    {
        if(i == s.size())
        {
            set.emplace(string(path.begin(), path.begin() + size));
            return;
        }
        path[size] = s[i];
        f2(s, path, i + 1, size + 1, set);
        f2(s, path, i + 1, size, set);
    }

public:
    vector<string> generatePermutation1(string s) 
    {
        unordered_set<string> set;
        string path;
        f1(s, path, 0, set);
        vector<string> ans(set.size());
        int i = 0;
        for(auto& str : set) ans[i++] = str;
        return ans;
    }

    vector<string> generatePermutation2(string s) 
    {
        unordered_set<string> set;
        string path(s.size(), ' ');
        f2(s, path, 0, 0, set);
        vector<string> ans(set.size());
        int i = 0;
        for(auto& str : set) ans[i++] = str;
        return ans;
    }
};